"""
时间复杂度：O(n**2)
"""
import random

from SortingAlgorithm.cal_time.cal_time import cal_time

# 冒泡排序
# 简单 在原来的列表上排序
@cal_time(name="冒泡排序时间")
def bubble_sort(li):
    for i in range(len(li)-1):
        exchange = False
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        if not exchange:
            return

# 基本 在原来的列表上排序
@cal_time()
def bubble_sort1(li, key=lambda a: a, reverse=False):
    for i in range(len(li)-1):
        exchange = False
        for j in range(len(li)-i-1):
            con = key(li[j]) < key(li[j+1]) if reverse else key(li[j]) > key(li[j+1])
            if con:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        if not exchange:
            return

# 简单 生成新的排序好了的列表
@cal_time()
def bubble_sort2(li):
    ret = []
    for i in li:
        for index, j in enumerate(ret):
            if i < j:
                ret.insert(index, i)
                break
        else:
            ret.append(i)
    return ret

# 基本 生成新的排序好了的列表
@cal_time()
def bubble_sort3(li, key=lambda a: a, reverse=False):
    ret = []
    # if reverse:
    #     con = lambda a, b: key(a) > key(b)
    # else:
    #     con = lambda a, b: key(a) < key(b)

    for i in li:
        for index, j in enumerate(ret):
            con = key(i) > key(j) if reverse else key(i) < key(j)
            if con:
                ret.insert(index, i)
                break
        else:
            ret.append(i)
    return ret

if __name__ == '__main__':
    # l = [1, 3, 2, 6, 8, 9, 2, 4, 7, 11, 5, 8, 24]
    l = list(range(10000))
    random.shuffle(l)
    ret = bubble_sort1(l)
    # print(l, ret)